剑指offer 27.字符串的排列

剑指offer 27.字符串的排列

题目

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

回溯法加上递归思路，找到所有可能的排列情况，全部加入到最后的结果集合中，这里要记得去重，最后输出。

代码

 public ArrayList<String> Permutation(String str) {
  ArrayList<String> resultList = new ArrayList<>();
  if (str.length() == 0) {
    return resultList;
  }
  fun(str.toCharArray(), resultList, 0);
  Collections.sort(resultList);

  return resultList;
}

public void fun(char[] ch, List<String> list, int i) {

  if (i == ch.length - 1) {
    if (!list.contains(new String(ch))) {
      list.add(new String(ch));
      return;
    }
  } else {
    for (int j = i; j < ch.length; j++) {
      swap(ch, i, j);
      fun(ch, list, i + 1);
      swap(ch, i, j);
    }
  }
}

public void swap(char[] str, int i, int j) {
  if (i != j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
  }
}